package SubjectTree.Four;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import Utility.TreeNode;

public class FindMode {

/**
 * 难度：简单
 * 
 * 501. 二叉搜索树中的众数
 * 	给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
 * 	假定 BST 有如下定义：
 * 		结点左子树中所含结点的值小于等于当前结点的值
 * 		结点右子树中所含结点的值大于等于当前结点的值
 * 		左子树和右子树都是二叉搜索树
 * 	
 * 例如：
 * 	给定 BST [1,null,2,2],
 * 	   1
 * 	    \
 * 	     2
 * 	    /
 * 	   2
 * 	返回[2].
 * 	
 * 提示：如果众数超过1个，不需考虑输出顺序
 * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FindMode fm = new FindMode();
		System.out.println(fm.findMode(TreeNode.MkTree("[1,null,2,null,null,2,null]")));
	}
	//自己写(中序遍历)
	public int[] findMode(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		TreeNode pre = null;
		int count = 1;
		int maxCount = 1;
		List<Integer> list = new ArrayList<>();
		while(!deque.isEmpty() || root!=null) {
			while(root!=null) {
				deque.push(root);
				root = root.left;
			}
			root = deque.pop();
			//中序,判断是否有重复得元素
			if(pre!=null && pre.val == root.val) {
				count++;
			}else {
				count=1;
			}
			pre = root;
			if(count==maxCount) {
				list.add(root.val);
			}
			if(count>maxCount) {
				maxCount = count;
				list.clear();
				list.add(root.val);
			}
			
			root = root.right;
		}
//		System.out.println(list);
		return list.stream().mapToInt(Integer::valueOf).toArray();
    }
	//自己写(递归)
	TreeNode pre = null;
	int count_1 = 1;
	int maxCount_1 = 1;
	List<Integer> list = new ArrayList<>();
	public int[] findMode_1(TreeNode root) {
		if(root == null) return new int[0];
		findMode_1(root.left);
		if(pre!=null && pre.val == root.val) {
			count_1++;
		}else {
			count_1=1;
		}
		pre = root;
		if(count_1==maxCount_1) {
			list.add(root.val);
		}
		if(count_1>maxCount_1) {
			maxCount_1 = count_1;
			list.clear();
			list.add(root.val);
		}
		findMode_1(root.right);
		return list.stream().mapToInt(Integer::valueOf).toArray();
    }
	//方法一：中序遍历
	List<Integer> answer = new ArrayList<Integer>();
    int base, count, maxCount;
    public int[] findMode1(TreeNode root) {
        dfs(root);
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }
    public void dfs(TreeNode o) {
        if (o == null) {
            return;
        }
        dfs(o.left);
        update(o.val);
        dfs(o.right);
    }
    public void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.add(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
    }
    //方法二：Morris 中序遍历
//    int base, count, maxCount;
//    List<Integer> answer = new ArrayList<Integer>();
    public int[] findMode2(TreeNode root) {
        TreeNode cur = root, pre = null;
        while (cur != null) {
            if (cur.left == null) {
                update2(cur.val);
                cur = cur.right;
                continue;
            }
            pre = cur.left;
            while (pre.right != null && pre.right != cur) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = cur;
                cur = cur.left;
            } else {
                pre.right = null;
                update2(cur.val);
                cur = cur.right;
            }
        }
        int[] mode = new int[answer.size()];
        for (int i = 0; i < answer.size(); ++i) {
            mode[i] = answer.get(i);
        }
        return mode;
    }
    public void update2(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.add(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer.clear();
            answer.add(base);
        }
    }
}
